// 归并排序，自底向上--对于小规模数组效率更有效

// 暴露接口
export function mergeSort(nums: number[]): number[] {
    sort(nums, 0, nums.length - 1);
    return nums;
}
// 主排序逻辑，这里的实现与自顶向下会不一样，是通过从前往后合并的
// 执行归并的过程频率减小，扫描的过程增多
function sort(nums: number[], start: number, end: number) {
    // subArrSize指当前分成的两个子数组的大小
    for (let subArrSize = 1; subArrSize < nums.length; subArrSize = subArrSize * 2) {
        // min + subArrSize - 1是中间边界，
        // 最后要取最小值是因为min + 2 * subArrSize - 1可能超出数组边界索引
        for (let min = 0; min < nums.length - subArrSize; min += subArrSize * 2) {
            merge(nums, min, min + subArrSize - 1, Math.min(end, min + 2 * subArrSize - 1));
        }
    }
}

// 归并逻辑，负责对两个有序的数组合并
function merge(nums: number[], start: number, mid: number, end: number) {
    const copyNums: number[] = [];// 待复制数组
    // 先复制要排序的数组
    for (let i = start; i <= end; i++) {
        copyNums[i] = nums[i];
    }
    // 基于双指针法进行归并，注意边界情况
    let left = start;
    let right = mid + 1;
    for (let i = start; i <= end; i++) {
        // 边界情况一，左数组已经被合并完
        if (left > mid) {
            nums[i] = copyNums[right];
            right++;
        } else if (right > end) {
            // 边界情况二，右数组已经被合并完
            nums[i] = copyNums[left];
            left++;
        } else if (copyNums[left] <= copyNums[right]) {
            // 正常情况，左边的数组比右边的数组小
            nums[i] = copyNums[left];
            left++;
        } else {
            // 正常情况，右边的数组比左边的数组小
            nums[i] = copyNums[right];
            right++;
        }
    }
}
